Software applications generally have a series of operations that are performed both sequentially and in parallel. Oftentimes, an operation will depend on a result from one or more other operations. Problems arise when a set of operations become interdependent on each other, where a first operation, directly or through intermediate operations, depends on the output of another operation, which in turn depends directly or through intermediate operations, on the first operation. These interdependencies can cause an application to fall into infinite loops where each operation is waiting for results from one or more other operations. These dependencies may be represented as a directed graph.
A directed graph is a structure containing a set of vertices, connected by edges that have a direction. Graph traversal is the process of visiting all of the vertices in the graph. The graph may be traversed by starting at one of the vertices and following the edges until each vertex that is reachable from that vertex has been visited. In the case of disconnected graphs, one may need to start traversal from various vertices. A cycle in a directed graph refers to a loop in the graph such that when traversing the edges away from a vertex, eventually we come back to the same node.
Referring to FIG. 1, a directed graph 100 is depicted. The directed graph includes three vertices 110, 115, 120 connected by three directed edges 125, 130, 135. The direction of each edge is indicated by an arrow at the end of each edge. The depicted graph 100 also forms a cycle starting at vertex A 110, traveling from vertex A 110 to vertex B 115 over edge AB 125, traveling from vertex B 115 to vertex C 120 over edge BC 130, and returning to vertex A 110 over edge CA 135.
In the context of software, vertex A (110) may signify a first operation, vertex B (115) may signify a second operation, and vertex C (120) may signify a third operation. The edges AB (125), BC (130), and CA (135) may signify dependencies between the operations. Thus, the first operation (vertex A) requires a result from the third operation (vertex C), the second operation (vertex B) requires a result from the first operation (vertex A), and the third operation (vertex C) requires a result from the second operation (vertex B). Thus, none of the operations can be completed because each operation is dependent on another operation resulting in an infinite loop.
Applications that fall into infinite dependency loops are often configured to automatically break out of these loops by removing a dependency (an edge in a graph) and accepting any repercussions caused by removing the dependency. In many instances, breaking a cycle does not cause an application to fail when run, but instead introduces inaccuracy into the analysis that the application was intended to perform. In cases where the options are for the application to be stuck in an infinite loop or for the application to produce a less accurate result, the less accurate result is the more desirable option.
Static timing analysis applications sometimes have issues related to dependency loops. Static timing analysis is related to computing the expected timing of a digital circuit. When designing a digital circuit, the designer must account for the various delays between different circuit elements so that the results of a series of operations in the circuit arrive at a destination at the correct time based on a clock signal. Since processing signals within a circuit may have dependencies on other signals, timing of the signals is critical. Similar to the hypothetical application above, the digital circuit may be depicted as a directional graph. In some cases, the digital circuit may have cycles leading to infinite dependency loops. In order to perform static timing analysis, the infinite loops must be broken at the expense of reduced accuracy.
Another example is in the field of datapath placement. A datapath includes a set of functional units connected to a system bus that operate to perform data processing operations. Similarly to the examples provided above, the datapath placement may include interdependencies between operations which may lead to loops if the function performing the operations needs to be placed in the direction of data flow, and if the data has a cyclic dependency. Again, by breaking the loop, a valid placement is obtained at the cost of increased inaccuracy of mimicking the data flow.
It is with these and other issues in mind that various aspects of the present disclosure were developed.